package leetcode_600;

/**
 *@author 周杨
 *SingleElementInASortedArray_540 一个排序数组里所有元素都出现了2次 只有一个元素出现了一次 请找出它
 *describe:用二分查找 每次查看符合要求的奇数数量的区间 AC 37%
 *2018年9月12日 上午9:59:33
 */
public class SingleElementInASortedArray_540 {
	public int singleNonDuplicate(int[] nums) {
        return help(nums,0,nums.length-1);
    }
	
	public int help(int []nums,int left,int right) {
		if(left==right)
			return nums[left];
		int mid=left+(right-left)/2;
		if(nums[mid]==nums[mid-1]) {//看左区间是否符合
			if((mid-1-left)%2!=0)
				return help(nums,left,mid-2);
			else
				return help(nums,mid+1,right);
		}
		else {
			if((right-mid-1)%2!=0)//右区间是奇数区间
				return help(nums,mid+2,right);
			return help(nums,left,mid-1);
		}
			
	}
}
